/**
 * 188. Best Time to Buy and Sell Stock IV 买卖股票的最佳时机IV
 * https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
 */
class BestTimeToBuyAndSellStockIV {
    /**
     * 方法： 使用动态规划求解最大利润
     *       f[j][0]表示完成j次交易且不持有股票的最大利润
     *       f[j][1]表示完成j-1次交易且持有股票的最大利润
     *       对于每个价格p:
     *       - 卖出股票: f[j][0] = max(f[j][0], f[j][1] + p)
     *       - 买入股票: f[j][1] = max(f[j][1], f[j-1][0] - p)
     *
     * Args:
     *      k: int - 最多允许完成的交易次数
     *      prices: int[] - 股票每天的价格数组
     *
     * Returns:
     *      int: 最多k次交易能获得的最大利润
     *
     * Time: O(n*k) - n为价格数组长度，k为最大交易次数
     *
     * Space: O(k) - 需要2*(k+2)大小的数组存储动态规划状态
     */
    public int maxProfit(int k, int[] prices) {
        int[][] f = new int[k+2][2];
        for(int j = 1; j <= k+1; j++){
            f[j][1] = Integer.MIN_VALUE / 2; //防止溢出
        }
        f[0][0] = Integer.MIN_VALUE / 2;
        for(int p : prices){
            for(int j = k+1; j > 0; j--){
                f[j][0] = Math.max(f[j][0], f[j][1] + p);
                f[j][1] = Math.max(f[j][1], f[j-1][0] - p);
            }
        }
        return f[k+1][0];
    }
}